package com.programmercarl.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode.cn/problems/n-queens/description/
 * N皇后问题    优化
 *
 * @author yulongtian
 * @create 2025-01-30 19:53
 */
public class Test14_1 {
    public static void main(String[] args) {
        Test14_1 test14 = new Test14_1();
//        List<String> list = Arrays.asList("..Q.", "Q...", "...Q", ".Q..");
        System.out.println(test14.solveNQueens(4));
    }

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>(n);
        Character[][] grid = new Character[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j] = '.';
            }
        }
        backTracking(n, 0, res, grid);
        return res;
    }

    public void backTracking(int n, int row, List<List<String>> res, Character[][] grid) {
        if (row == n) {
            res.add(Array2List(grid));
            return;
        }

        for (int i = 0; i < n; i++) {
            grid[row][i] = 'Q';
            if (!check(grid, row, i)) {
                grid[row][i] = '.';
                continue;
            }
            backTracking(n, row + 1, res, grid);
            grid[row][i] = '.';
        }
    }

    public List<String> Array2List(Character[][] grid) {
        List<String> list = new ArrayList<>();
        for (int i = 0; i < grid.length; i++) {
            StringBuilder sb = new StringBuilder(grid[i].length);
            for (int j = 0; j < grid[i].length; j++) {
                sb.append(grid[i][j]);
            }
            list.add(sb.toString());
        }
        return list;
    }


    public boolean check(Character[][] grid, int row, int col) {
        // 列
        for (int i = 0; i < row; i++) {
            if (grid[i][col] == 'Q') {
                return false;
            }
        }

        // 45° col+1,row-1
        for (int i = row - 1, j = col + 1; i >= 0 && j < grid[0].length; i--, j++) {
            if (grid[i][j] == 'Q') {
                return false;
            }
        }


        // 135° col-1 row-1
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (grid[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
}
